/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._10_05;

/**
 *
 * 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
 *
 * 示例1:
 *
 *  输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
 *  输出：-1
 *  说明: 不存在返回-1。
 * 示例2:
 *
 *  输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 *  输出：4
 * 提示:
 *
 * words的长度在[1, 1000000]之间
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._10_05
 * @ClassName: FindString
 * @Author: linyaonan
 * @Date: 2020/3/31 16:58
 */
public class FindString {

    public int findString(String[] words, String s) {
        int start = 0;
        int end = words.length - 1;
        while (start <= end) {
            // 临时中间节点
            int tempMid = start + ((end - start) >> 1);
            int mid = -1;
            if (!isNotNull(words[tempMid])) {

                int org = tempMid;
                while (true) {
                    boolean endIsDone = false;
                    // 一直向后查找
                    if (tempMid <= end) {
                        if (!isNotNull(words[tempMid])) {
                            tempMid++;
                        } else {
                            mid = tempMid;
                            break;
                        }
                    } else {
                        endIsDone = true;
                    }
                    // 一直向前查找
                    if (org >= start) {
                        if (!isNotNull(words[org])) {
                            org--;
                        } else {
                            mid = org;
                            break;
                        }
                    } else {
                        if (endIsDone) {
                            // 前后都没有合适的字符串
                            return -1;
                        }
                    }

                }
            } else {
                // 有效位
                mid = tempMid;
            }
            // 没有找到有效值
            if (mid == -1) {
                return -1;
            }
            String v = words[mid];
            int i = s.compareTo(v);
            if (i == 0) {
                return mid;
            } else if (i > 0) {
                start = mid + 1;
            } else if (i < 0) {
                end = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 判断字符串有效
     * @param s
     * @return
     */
    private boolean isNotNull(String s) {
        return !"".equals(s);
    }

}
